//
//  MinimumCostAnalyzer.cpp
//  RoutingEvaluator
//
//  Created by Christopher Kemsley on 4/15/12.
//  Copyright (c) 2012 iAppolopolis. All rights reserved.
//

#import <Foundation/Foundation.h>
#include <set>
#import "Analyzer.hpp"
#import "Node.hpp"
#import "Link.hpp"
#import "OCNodeInfo.h"
#import "OCLinkInfo.h"
#import "BIPNode.h"
#import "BIPLink.h"

NamespaceBegin



struct BIPAnalyzer : Analyzer
{
	BIPAnalyzer () : Analyzer ( "Broadcast Incremental Power" ) { }
	
	
	virtual void	analyze		( NodeInfoSet * nodesInfo , LinkInfoSet * linksInfo , PropertySet const & info , Output & output )
		{
		Float64		maxRange=	20 ; // 20 is the default
		info . getValue ( "maxRange" , maxRange ) ;
		
		UInteger	startNode=	1 ;
		info . getValue ( "referenceNode" , startNode ) ;
		
		
		
		NodeSet	*	nodes	=	NodeSet :: createSetWithNodes(nodesInfo) ;
		LinkVector	links ;
		
		
		
		
		
		generateTopology ( nodesInfo , linksInfo , maxRange , startNode , nodes , links ) ;
		
		
		
		
		
		// Calculate the sum
		
		Float64		sum		=	0 ;
		UInteger	txCount	=	0 ;
		
		// Changes 'links' to reflext only used links
		calculateCost ( nodes , links , startNode , sum , txCount ) ;
		
		output.tableOut() << "Property	Value" ;
		
		output.tableOut() << "\nTotal Energy	" << sum ;
		output.tableOut() << "\nTransmission Count	" << txCount ;
		
		
		
		
		
		output.drawNetworkTopology ( nodes , links ) ;
		}
	
	
	
	static void		generateTopology ( NodeInfoSet * nodesInfo , LinkInfoSet * linksInfo , Float64 maxRange , UInteger startNodeID , NodeSet * nodes , LinkVector & links )
		{
		/* These'll help us sort things */
		
		NSSortDescriptor*	sorter		=	[NSSortDescriptor sortDescriptorWithKey:@"minimumPowerIncrement" ascending:YES] ;
		NSArray*			sorters		=	[NSArray arrayWithObject:sorter] ;
		
		
		
		
		/* Setup all the nodes/links */
		
		NSSet		*	allLinks		=	[BIPLink linkInfoSet:linksInfo] ;
		NSSet		*	allNodes		=	[BIPNode setWithNodes:nodesInfo allLinks:allLinks] ;
		
		BIPNode		*	startNode		=	0 ;
		
		
		/* Put some things in place */
		
		for ( BIPLink * link in allLinks )
			{
			[link replaceEndpointObjects:allNodes] ;
			}
		
		for ( BIPNode * node in allNodes )
			{
			if ( node.identifier == startNodeID )
				{
				startNode = node ;
				break ;
				}
			}
		
		if ( startNode == 0 )
			[NSException raise:NSInternalInconsistencyException format:@"Start node with ID %u not found",startNodeID] ;
		
		__block NSSet * activeSet = [NSSet setWithObject:startNode] ;
		
		
		
		
		/* Simple functions */
		
		BOOL (^hasUntouchedNodes)(void) = ^BOOL{
			return ! [activeSet isEqual:allNodes] ;
		} ;
		NSSet* (^activeNodes)(void) = ^NSSet*{
			NSMutableSet * set = [NSMutableSet setWithCapacity:allNodes.count] ;
			for ( BIPNode * node in allNodes )
				{
				if ( node.activeLinks.count != 0 )
					[set addObject:node] ;
				}
			return set ;
		} ;
		
		
		
		
		/* Algorithm */
		
		while ( hasUntouchedNodes() )
			{
			NSArray	*	sorted			=	[activeSet sortedArrayUsingDescriptors:sorters] ;
			
			BIPNode	*	smallest		=	[sorted objectAtIndex:0] ;
			
			[smallest activateNextLinks] ;
			
			activeSet = activeNodes() ;
			}
		
		
		
		
		/* Assemble the output data */
		
		for ( BIPLink * linkID in allLinks )
			{
			if ( ! linkID.isActive ) continue ;
			
			NSArray	*	nodeInfos	=	[linkID.endpoints allObjects] ;
			if ( nodeInfos.count != 2 )
				[NSException raise:NSInternalInconsistencyException format:@"Expected two endpoints, but got: %@",nodeInfos] ;
			
			OCNodeInfo	*	nodeID1	=	[nodeInfos objectAtIndex:0] ;
			OCNodeInfo	*	nodeID2	=	[nodeInfos objectAtIndex:1] ;
			Node		*	node1	=	nodes -> nodeWithNodeInfo ( nodeID1.info ) ;
			Node		*	node2	=	nodes -> nodeWithNodeInfo ( nodeID2.info ) ;
			Link		*	link	=	Link :: createLink ( linkID.info , node1 , node2 ) ;
			links . push_back ( link ) ;
			}
		}
	
	
	
	static void		calculateCost	( NodeSet * nodes , LinkVector & activeLinks , UInteger startNodeID , Float64 & cost , UInteger & txCount )
		{
		__block std::set<Node*>		visitedNodes ;
		__block std::set<Node*>		unvisitedNodes ;
		__block LinkVector			usedLinks ;
		
		cost = 0 ;
		txCount = 0 ;
		
		
		/* Setup the visited/unvisited node sets */
		
		std::vector<Node*>::const_iterator	here	=	nodes->nodes().begin() ;
		std::vector<Node*>::const_iterator	end		=	nodes->nodes().end() ;
		while ( here < end )
			{
			Node * n = *(here++) ;
			if ( n->identity->identifier == startNodeID )
				visitedNodes . insert ( n ) ;
			else
				unvisitedNodes . insert ( n ) ;
			}
		
		if ( visitedNodes.size() != 1 )
			[NSException raise:NSInternalInconsistencyException format:@"Start node ID should have had one match; instead, had %u",(unsigned)visitedNodes.size()] ;
		
		
		
		
		
		
		/* Simple functions */
		
		BOOL (^nodeHasBeenVisited) (Node * node) = ^BOOL(Node*node){
			return visitedNodes.find(node) != visitedNodes.end() ;
		} ;
		Node* (^nodeOnOtherSideOfLink)(Node*,Link*) = ^Node* ( Node* oppositeThisNode , Link* onThisLink ) {
			if ( onThisLink->endpoint1 == oppositeThisNode )
				return onThisLink->endpoint2 ;
			return onThisLink->endpoint1 ;
		} ;
		
		Float64	(^maxCostOfTXToUnvisitedNode) ( Node * forThisNode ) = ^Float64(Node*node){
			Float64	maxCost		=	0 ;
			bool	didMatch	=	false ;
			
			std::vector<Link*>::const_iterator	here	=	node->links().begin() ;
			std::vector<Link*>::const_iterator	end		=	node->links().end() ;
			while ( here < end )
				{
				Link * l = *(here++) ;
				
				if ( ! nodeHasBeenVisited ( nodeOnOtherSideOfLink(node,l) ) )
					{
					Float64 c = l->identity->cost() ;
					if ( c > maxCost )
						maxCost = c ;
					didMatch = YES ;
					}
				}
			
			if ( didMatch ) return maxCost ;
			else			return kFloat64Max ;
		} ;
		
		LinkVector const (^nodeLinksUnderCost) ( Node* forThisNode , Float64 maxCost ) = ^LinkVector const(Node*node,Float64 max){
			LinkVector v ;
			std::vector<Link*>::const_iterator	here	=	node->links().begin() ;
			std::vector<Link*>::const_iterator	end		=	node->links().end() ;
			while ( here < end )
				{
				Link * l = *(here++) ;
				Float64 c = l->identity->cost() ;
				if ( c <= max )
					v.push_back(l) ;
				}
			return v ;
		} ;
		
		void (^markBothEndpointsVisited) ( Link * forThisLink ) = ^(Link*link){
			unvisitedNodes . erase ( link->endpoint1 ) ;
			unvisitedNodes . erase ( link->endpoint2 ) ;
			visitedNodes . insert ( link->endpoint1 ) ;
			visitedNodes . insert ( link->endpoint2 ) ;
		} ;
		void (^markAllEndpointsVisited) ( LinkVector const & forTheseLinks ) = ^(LinkVector const & links){
			LinkVector::const_iterator here = links.begin() ;
			LinkVector::const_iterator end  = links.end() ;
			while ( here < end )
				markBothEndpointsVisited ( *(here++) ) ;
		} ;
		
		
		
		
		
		
		/* Algorithm */
		
		while ( unvisitedNodes.size() != 0 )
			{
			std::set<Node*>::iterator	here	=	visitedNodes.begin() ;
			std::set<Node*>::iterator	end		=	visitedNodes.end() ;
			while ( here != end )
				{
				Node * node = *(here++) ;
				
				Float64 itsMaxCost = maxCostOfTXToUnvisitedNode ( node ) ;
				
				// If it's the max, that means it's already complete
				if ( itsMaxCost != kFloat64Max )
					{
					cost += itsMaxCost ;
					
					LinkVector linksItUses = nodeLinksUnderCost ( node , itsMaxCost ) ;
					
					markAllEndpointsVisited ( linksItUses ) ;
					
					usedLinks . insert ( usedLinks.end() , linksItUses.begin() , linksItUses.end() ) ;
					
					txCount ++ ;
					
					break ;
					}
				}
			}
		
		
		
		activeLinks = usedLinks ;
		}
	
	
	
	
	
	
} ;




BIPAnalyzer _BIPAnalyzer ;

NamespaceEnd
